Лабораторна робота №1. Тема: Комбінаторика (Розміщення, перестановки, комбінації, біном Ньютона) Комбінаторика – це галузь математики, предметом якої є теорія скінченних множин. Значна кількість теорем і формул комбінаторики ґрунтується на двох елементарних правилах, які називаються правилами суми і добутку. Правило суми - якщо деякий об’єкт a можна вибрати m способами, а об’єкт b – n способами, причому ніякий вибір a не збігається з жодним з виборів b, то один з об’єктів a або b можна вибрати m+n способами. Правило добутку – якщо деякий об’єкт a можна вибрати m способами і при кожному виборі об’єкта a об’єкт b можна вибрати n способами, то вибір пари (a, b) можна здійснити mn способами. Правило суми та добутку можна узагальнити на будь-яку більшу кількість об’єктів. У комбінаториці розглядають три типи сполук – розміщення, перестановки та комбінації. Розміщення з n елементів по m називають сполуки, що складаються з m елементів, взятих з n, і відрізняються або складом елементів, або їх порядком. Кількість всіх можливих розміщень розраховують за формулою: без повторень - з повтореннями  EMBED Equation.3 
  EMBED Equation.3 
 Перестановками n елементів називають сполуки, що відрізняються тільки порядком елементів. Кількість всіх можливих перестановок розраховують за формулою: без повторень - з повтореннями  EMBED Equation.3 
  EMBED Equation.3 
 Комбінаціями з n елементів по m називають сполуки, що складаються з m елементів, взятих з n, і відрізняються тільки складом (порядок не має значеня). Кількість всіх можливих комбінацій розраховують за формулою: без повторень - з повтореннями  EMBED Equation.3 
  EMBED Equation.3 
 Алгоритм генерування лексикографічно наступної перестановки
Алгоритм генерування лексикографічно наступної сполуки n-елементної множини X={1,2,…,n} по r елементів.
Біном Ньютона (n - додатнє ціле):
Завдання Запрограмувати за варіантом обчислення кількості комбінацій розміщення (перестановок, комбінацій, алгоритму визначення наступної лексикографічної сполуки, перестановки) та формулу бінома Ньютона і побудувати за допомогою неї розклад за варіантом. Варіант 1. Задане додатне ціле число n. Розташувати у лексикографічному порядку всі перестановки множини {1,2,…,n}. Побудувати розклад (x+y)5. Варіант 2. Задане додатне ціле число n і невід’ємне ціле число r, (r<=n). Розташувати у лексикографічному порядку всі сполуки без повторень із r елементів множини {1,2,…,n}. Побудувати розклад (x-y)5. Варіант 3. Задане додатне ціле число n і невід’ємне ціле число r, (r<=n). Розташувати у лексикографічному порядку всі розміщення без повторень із r елементів множини {1,2,…,n}. Побудувати розклад (x+y)6. Варіант 4. Задане додатне ціле число n. Побудувати всі сполуки без повторень елементів множини {1,2,…,n}. Побудувати розклад (x-y)6. Варіант 5. Задане додатні цілі числа n та r. Побудувати у лексикографічному порядку всі розміщення з повтореннями із r елементів множини {1,2,…,n}. Побудувати розклад (x+y)7. Варіант 6. Задане додатні цілі числа n та r. Побудувати у лексикографічному порядку всі сполуки з повтореннями із r елементів множини {1,2,…,n}. Побудувати розклад (x-y)7. Варіант 7. Визначити лексикографічно наступну перестановку для кожної з перестановок: 1432, 54123, 12453, 45231, 6714235, 31528764. Побудувати розклад (x-y)8. Варіант 8. Розташувати наведені перестановки елементів множити {1,2,3,4,5,6} у лексикографічному порядку: 234561, 231456, 165432, 156423, 543216, 541236, 231465, 314562, 432561, 654321, 654312, 435612. Побудувати розклад (x+y)8. Варіант 9. Використовуючи алгоритм побудови лексикографічно наступної перестановки, записати перші 12 перестановок елементів множини {1,2,3,4,5,6}. Побудувати розклад (x-y)9. Варіант 10. Використовуючи алгоритм побудови лексикографічно наступної сполуки, виписати всі сполуки по 4 елементи множини {1,2,3,4,5,6}. Побудувати розклад (x+y)9.